ОЦЕНКИ ВЫСОКОЙ СТЕПЕНИ ТОЧНОСТИ ДЛЯ СЛОЖНОСТИ БУЛЕВЫХ ФОРМУЛ В НЕКОТОРЫХ БАЗИСАХ ИЗ ЭЛЕМЕНТОВ С ПРЯМЫМИ И ИТЕРАТИВНЫМИ ВХОДАМИ

Ложкин Сергей Андреевич, доктор физико-математических наук, профессор, кафедра математической кибернетики, Московский государственный университет имени М. В. Ломоносова (Россия, г. Москва, Ленинские горы, 1), lozhkin@cs.msu.ru
Коноводов Владимир Александрович, аспирант, Московский государственный университет имени М. В. Ломоносова (Россия, г. Москва, Ленинские горы, 1), vkonovodov@gmail.com

519.714

Актуальность и цели. В математической кибернетике одной из основных задач является задача синтеза управляющих систем, заключающаяся в построении схемы из заданного класса, которая реализует заданную функцию алгебры логики. При решении этой задачи часто требуется учитывать различного рода ограничения на структуру и параметры управляющих систем. Такие ограничения ча-
сто более точно описывают реальные вычисления, а исследование сложности функций в моделях с ограничениями представляет большой теоретический интерес. Рассматриваемое в данной работе ограничение относится к способам соединения элементов в схеме. Входы элементов схем делятся на два типа – прямые и итеративные. Итеративные входы служат для присоединения к ним выходов других элементов, а прямые входы являются входами схем. Задача синтеза в этой модели рассматривается для случая формул, т.е. схем без ветвлений выходов элементов. Целью данной работы является получение оценок функции Шеннона высокой степени точности для сложности формул в некоторых полных базисах указанного типа, т.е. оценок, в которых устанавливается асимптотика второго члена асимптотического разложения этой функции. Ранее была получена только асимптотика функции Шеннона для базисов, итеративное замыкание которых содержит класс монотонных функций, оценки высокой степени точности для широких классов базисов в этой модели известны не были.
Материалы и методы. В работе, в частности, приводится модификация известного ранее оптимального метода синтеза формул с использованием техники моделирования функций алгебры логики переменными на компонентах специальных разбиений множества наборов булева куба. В основе конструкции лежит построение специальных формул, которые реализуют функции, имеющие селекторные разбиения множества своих переменных с константной энтропией.
Результаты. Получены оценки высокой степени точности функции Шеннона для сложности формул алгебры логики в некоторых полных базисах с прямыми и итеративными переменными, итеративное замыкание которых содержит класс монотонных функций.
Выводы. Впервые в классе формул в базисах с прямыми и итеративными входами выделен достаточно широкий подкласс, в котором получены оценки высокой степени точности функции Шеннона для их сложности.

булевы формулы, прямые и итеративные переменные, синтез, сложность, функция Шеннона, асимптотические оценки высокой степени точности.

1. Ложкин, С. А. О полноте и замкнутых классах функций алгебры логики с прямыми и итеративными переменными / С. А. Ложкин // Вестник Московского университета. Сер. 15. Вычислительная математика и кибернетика. – 1999. – № 3. – С. 35–41.
2. Ложкин, С. А. О сложности реализации функций алгебры логики схемами и формулами, построенными из функциональных элементов с прямыми и итеративными входами / С. А. Ложкин // Дискретные модели в теории управляющих систем : тр. III Междунар. конф. (Красновидово, 22–28 июня 1998 г.). – М. : Диалог-МГУ, 1998. – С. 72–73.
3. Ложкин, С. А. О сложности формул алгебры логики в некоторых полных базисах, состоящих из элементов с прямыми и итеративными входами / С. А. Ложкин, В. А. Коноводов // Известия высших учебных заведений. Поволжский регион. Физико-математические науки.–2015.—№1(31).–С.55–68.
4. Коноводов, В. А. Некоторые особенности задачи синтеза булевых формул в полных базисах с прямыми и итеративными входами / В. А. Коноводов // Ученые записки Казанского университета. Сер. Физико-математические науки. – 2014. – Т. 156, № 3. – С. 76–83.
5. Яблонский, С. В. Введение в дискретную математику / С. В. Яблонский. – М. : Наука, 1986. – 384 с.
6. Ложкин, С. А. Лекции по основам кибернетики / С. А. Ложкин. – М. : МАКС Пресс, 2004. – 256 с.
7. Ложкин, С. А. Оценки высокой степени точности для сложности управляющих систем из некоторых классов / С. А. Ложкин // Математические вопросы кибернетики.–1996.–№6.–С.189–213.
8. Ложкин, С. А. О синтезе формул, сложность и глубина которых не превосходят асимптотически наилучших оценок высокой степени точности / С. А. Ложкин // Вестник Московского университета. Сер. 1. Математика и механика. – 2007. – № 3. – С. 19–25.